problem

輸入為兩個不為空、元素皆為整數的陣列，回傳相差最小的一組數字 [a, b]，其中 a 來自第一個陣列，b 來自第二個陣列。可以確定只會有一組解。

sample input:
arrayOne = [-1, 5, 10, 20, 28, 3]
arrayTwo = [26, 134, 135, 15, 17]

sample output:
[28, 26]

這題一個有效但不怎麼快的解法是分別迴圈過兩個陣列，比較所有可能的組合，並持續更新記錄來找出差距最小的數字。

為了要做到只看部分組合，第二個方法嘗試利用處理陣列的常見手段 -- 排序，以有序陣列的特性來解題。

假設現在有兩個有序陣列 x, y，任意從其中各找出一個數字 x3, y5，如果 x3 == y5，差距為 0，則 [x3, y5] 一定就是解答。否則，如果 x3 < y5，則 x3 前面更小的所有數字，以及 y5 後面更大的所有數字，都只會讓差距更大，所以不需要再考慮。接下來只需要比較 x 陣列上比 x3 大或 y 陣列上比 y5 小的數字。

延伸上述想法，可以換成從陣列的開頭進行演算法來解這題：

1. 將兩個陣列排序，並以兩個指標指向兩陣列的第一個數字，
   arrayOne = [-1, 3, 5, 10, 20, 28]
   arrayTwo = [15, 17, 26, 134, 135]
2. 比較兩個數字，若不相等，則記錄下當前最小的差距及數組，例如 16, [-1, 15]。若相等可以直接回傳結果。
3. 若數字一 < 數字二，則指標一 + 1，否則指標二 + 1。
   例如目前 -1 < 15，因此將指標一右移，讓兩數差距縮小，下一輪就比較 3, 15。
4. 指標在陣列範圍內重複步驟 2-3，最後回傳結果。

這題的解法和前面的 two/ three number sum 類似，都是利用有序陣列和指標的方式，可以較優化地尋找趨近於某個值的數組，而不用把所有的可能組合都看過一遍。

如果 n 為陣列一長度，m 為陣列二長度，時間空間複雜度為
time: O(nlog(n) + mlog(m)) 因為陣列長度不一定一樣，這是排序兩個陣列的時間。
space: O(1) 這是原地排序的情況，可以詢問是否可以原地排序。

function smallestDifference(arrayOne, arrayTwo) {
  arrayOne.sort((a, b) => a - b);
  arrayTwo.sort((a, b) => a - b);
  let idxOne = 0;
  let idxTwo = 0;
  // 初始化為 Infinity 則無論一開始差距多大都可以更新
  let smallest = Infinity; // 最小差距
  let current = Infinity; // 當前兩數的差距
  let pair = [];

  while (idxOne < arrayOne.length && idxTwo < arrayTwo.length) {
    let firstNum = arrayOne[idxOne];
    let secondNum = arrayTwo[idxTwo];
    if (firstNum < secondNum) {
      current = secondNum - firstNum;
      idxOne++;
    } else if (firstNum > secondNum) {
      current = firstNum - secondNum;
      idxTwo++;
    } else {
      return [firstNum, secondNum];
    }
    if (smallest > current) {
      smallest = current;
      pair = [firstNum, secondNum];
    }
  }
  return pair;
}